home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ccdl151s.zip / SOURCE / ANALYZE.C < prev    next >
C/C++ Source or Header  |  1997-06-14  |  21KB  |  581 lines
  1. /*
  2.  * 68K/386 32-bit C compiler.
  3.  *
  4.  * copyright (c) 1997, David Lindauer
  5.  * 
  6.  * This compiler is intended for educational use.  It may not be used
  7.  * for profit without the express written consent of the author.
  8.  *
  9.  * It may be freely redistributed, as long as this notice remains intact
  10.  * and either the original sources or derived sources 
  11.  * are distributed along with any executables derived from the originals.
  12.  *
  13.  * The author is not responsible for any damages that may arise from use
  14.  * of this software, either idirect or consequential.
  15.  *
  16.  * v1.35 March 1997
  17.  * David Lindauer, gclind01@starbase.spd.louisville.edu
  18.  *
  19.  * Credits to Mathew Brandt for original K&R C compiler
  20.  *
  21.  */
  22. #include        <stdio.h>
  23. #include                "list.h"
  24. #include        "expr.h"
  25. #include        "c.h"
  26. #include        "errors.h"
  27. #include                 "diag.h"
  28.  
  29. extern int cf_freeaddress,cf_freedata,cf_freefloat;
  30. extern long framedepth,stackdepth;
  31. extern LIST *varlisthead;
  32. extern int lc_maxauto;
  33. extern int stackadd, stackmod;
  34.  
  35. int floatregs = 1,dataregs=1,addrregs = 1;
  36. CSE       *olist;         /* list of optimizable expressions */
  37. /*
  38.  *      this module will step through the parse tree and find all
  39.  *      optimizable expressions. at present these expressions are
  40.  *      limited to expressions that are valid throughout the scope
  41.  *      of the function. the list of optimizable expressions is:
  42.  *
  43.  *              constants
  44.  *              global and static addresses
  45.  *              auto addresses
  46.  *              contents of auto addresses.
  47.  *
  48.  *      contents of auto addresses are valid only if the address is
  49.  *      never referred to without dereferencing.
  50.  *
  51.  *      scan will build a list of optimizable expressions which
  52.  *      opt1 will replace during the second optimization pass.
  53.  */
  54.  
  55.  
  56. int equalnode(ENODE *node1, ENODE *node2)
  57. /*
  58.  *      equalnode will return 1 if the expressions pointed to by
  59.  *      node1 and node2 are equivalent.
  60.  */
  61. {       if( node1 == 0 || node2 == 0 )
  62.                 return 0;
  63.         if( node1->nodetype != node2->nodetype )
  64.                 return 0;
  65.                 if (natural_size(node1) != natural_size(node2))
  66.                                 return 0;
  67.         if( (isintconst(node1->nodetype) || node1->nodetype == en_labcon ||
  68.                         node1->nodetype == en_autoreg || node1->nodetype == en_nalabcon ||
  69.             node1->nodetype == en_nacon || node1->nodetype == en_napccon
  70.                         || node1->nodetype == en_autocon || node1->nodetype == en_absacon) &&
  71.             node1->v.i == node2->v.i )
  72.                 return 1;
  73.                 if ((node1->nodetype==en_rcon ||node1->nodetype==en_lrcon ||node1->nodetype==en_fcon) && node1->v.f == node2->v.f)
  74.                     return 1;
  75.         if( lvalue(node1) && equalnode(node1->v.p[0], node2->v.p[0]) )
  76.                 return 1;
  77.         return 0;
  78. }
  79.  
  80. CSE *searchnode(ENODE *node)
  81. /*
  82.  *      searchnode will search the common expression table for an entry
  83.  *      that matches the node passed and return a pointer to it.
  84.  */
  85. {       CSE     *csp;
  86.         csp = olist;
  87.         while( csp != 0 ) {
  88.                 if( equalnode(node,csp->exp) )
  89.                         return csp;
  90.                 csp = csp->next;
  91.                 }
  92.         return 0;
  93. }
  94.  
  95. ENODE *copynode(ENODE *node)
  96. /*
  97.  *      copy the node passed into a new enode so it wont get
  98.  *      corrupted during substitution.
  99.  */
  100. {       ENODE    *temp;
  101.         if( node == 0 )
  102.                 return 0;
  103.         temp = xalloc(sizeof(ENODE));
  104.                 temp->cflags = node->cflags;
  105.         temp->nodetype = node->nodetype;
  106.         temp->v.p[0] = node->v.p[0];
  107.         temp->v.p[1] = node->v.p[1];
  108.         return temp;
  109. }
  110.  
  111. CSE *enternode(ENODE *node,int duse,int size)
  112. /*
  113.  *      enternode will enter a reference to an expression node into the
  114.  *      common expression table. duse is a flag indicating whether or not
  115.  *      this reference will be dereferenced.
  116.  */
  117. {       CSE      *csp;
  118.                 if (size == 0)
  119.                     size = natural_size(node);
  120.         if( (csp = searchnode(node)) == 0 ) {   /* add to tree */
  121.                 csp = xalloc(sizeof(CSE));
  122.                 csp->next = olist;
  123.                 csp->uses = 1;
  124.                                 csp->reg = -1;
  125.                 csp->duses = (duse != 0);
  126.                 csp->exp = copynode(node);
  127.                 csp->voidf = 0;
  128.                                 csp->size = size;
  129.                 olist = csp;
  130.                 return csp;
  131.                 }
  132.                 else
  133.                     if (chksize(csp->size,size))
  134.                         csp->size = size;
  135.         ++(csp->uses);
  136.         if( duse )
  137.                 ++(csp->duses);
  138.         return csp;
  139. }
  140.  
  141. CSE *voidauto(ENODE *node)
  142. /*
  143.  *      voidauto will void an auto dereference node which points to
  144.  *      the same auto constant as node.
  145.  */
  146. {       CSE      *csp;
  147.         csp = olist;
  148.         while( csp != 0 ) {
  149.                 if( lvalue(csp->exp) && equalnode(node,csp->exp->v.p[0]) ) {
  150.                         if( csp->voidf )
  151.                                 return 0;
  152.                         csp->voidf = 1;
  153.                         return csp;
  154.                         }
  155.                 csp = csp->next;
  156.                 }
  157.         return 0;
  158. }
  159.  
  160. void voidall(void)
  161. /*
  162.  * Go through the CSP list voiding any use of a variable that
  163.  * has its address taken.
  164.  */
  165. {
  166.                 CSE *csp;
  167.                 csp = olist;
  168.                 while (csp) {
  169.                     if (csp->exp->nodetype == en_autocon || csp->exp->nodetype == en_autoreg) {
  170.                         CSE *two = voidauto(csp->exp);
  171.                         if (two) {
  172.                             csp->uses += two->duses;
  173.                         }
  174.                     }
  175.                     csp = csp->next;
  176.                 }
  177. }
  178. void scanexpr(ENODE *node, int duse,int size)
  179. /*
  180.  *      scanexpr will scan the expression pointed to by node for optimizable
  181.  *      subexpressions. when an optimizable expression is found it is entered
  182.  *      into the tree. if a reference to an autocon node is scanned the
  183.  *      corresponding auto dereferenced node will be voided. duse should be
  184.  *      set if the expression will be dereferenced.
  185.  */
  186. {       CSE      *csp, *csp1;
  187.                 int sz;
  188.         if( node == 0 )
  189.                 return;
  190.         switch( node->nodetype ) {
  191.                 case en_rcon: case en_lrcon: case en_fcon:
  192.                 case en_icon:
  193.                                 case en_lcon:
  194.                                 case en_iucon:
  195.                                 case en_lucon:
  196.                                 case en_ccon:
  197.                         enternode(node,duse,size);
  198.                         break;
  199.                 case en_napccon:
  200.                 case en_nacon:
  201.                                 case en_absacon:
  202.                 case en_autocon:
  203.                 case en_autoreg:
  204.                         enternode(node,duse,4);
  205.                         break;
  206.                                 case en_bits:
  207.                                             scanexpr(node->v.p[0],duse,0);
  208.                                             break;
  209.                                 case en_floatref:
  210.                                 case en_doubleref:
  211.                                 case en_longdoubleref:
  212.                 case en_b_ref:
  213.                 case en_w_ref:
  214.                 case en_ul_ref:
  215.                 case en_l_ref:
  216.                 case en_ub_ref:
  217.                 case en_uw_ref:
  218.                                                 if (node->v.p[0]->nodetype == en_autocon ||
  219.                                                         node->v.p[0]->nodetype == en_autoreg)
  220.                                                             enternode(node,duse,size);
  221.                                                 else
  222.                           scanexpr(node->v.p[0],1,natural_size(node));
  223.                         break;
  224.                 case en_uminus:
  225.                 case en_compl:  case en_ainc:
  226.                 case en_adec:   case en_not:
  227.                         scanexpr(node->v.p[0],duse,0);
  228.                         break;
  229.                                 case en_cb: case en_cub:
  230.                                 case en_cw: case en_cuw:
  231.                                 case en_cl: case en_cul:
  232.                                 case en_cf: case en_cd: case en_cp: case en_cld:
  233.                         scanexpr(node->v.p[0],duse,natural_size(node));
  234.                         break;
  235.                 case en_asadd:  case en_assub:
  236.                                                 size = natural_size(node->v.p[0]);
  237.                         scanexpr(node->v.p[0],duse,0);
  238.                         scanexpr(node->v.p[1],duse,size);
  239.                         break;
  240.                 case en_add:    case en_sub:
  241.                         scanexpr(node->v.p[0],duse,0);
  242.                         scanexpr(node->v.p[1],duse,0);
  243.                         break;
  244.                                 case en_asalsh: case en_asarsh: case en_alsh: case en_arsh:
  245.                 case en_asmul:  case en_asdiv:
  246.                 case en_asmod:  case en_aslsh:
  247.                                 case en_asumod: case en_asudiv: case en_asumul:
  248.                 case en_asrsh:  case en_asand:
  249.                 case en_assign: case en_refassign:
  250.                                 case en_asor:  case en_asxor:
  251.                                                 size = natural_size(node->v.p[0]);
  252.                         scanexpr(node->v.p[0],0,0);
  253.                         scanexpr(node->v.p[1],0,size);
  254.                         break;
  255.                                 case en_void:
  256.                                 case en_pmul:        case en_pdiv:
  257.                 case en_mul:    case en_div:
  258.                 case en_umul:    case en_udiv: case en_umod:
  259.                 case en_lsh:    case en_rsh:
  260.                 case en_mod:    case en_and:
  261.                 case en_or:     case en_xor:
  262.                 case en_lor:    case en_land:
  263.                 case en_eq:     case en_ne:
  264.                 case en_gt:     case en_ge:
  265.                 case en_lt:     case en_le:
  266.                                 case en_ugt:    case en_uge: case en_ult: case en_ule:
  267.                 case en_cond:
  268.                                 case en_moveblock: case en_stackblock: case en_callblock:
  269.                                 case en_pcallblock:
  270.                         scanexpr(node->v.p[0],0,0);
  271.                         scanexpr(node->v.p[1],0,0);
  272.                         break;
  273.                 case en_fcall: case en_intcall: case en_fcallb:
  274.                                 case en_pfcall: case en_pfcallb:
  275.                 case en_trapcall:
  276. /*                        scanexpr(node->v.p[0],1,0);
  277. */                        scanexpr(node->v.p[1],0,0);
  278.                         break;
  279.                 }
  280. }
  281.  
  282. void scan(SNODE *block)
  283. /*
  284.  *      scan will gather all optimizable expressions into the expression
  285.  *      list for a block of statements.
  286.  */
  287. {       while( block != 0 ) {
  288.                 switch( block->stype ) {
  289.                         case st_return:
  290.                         case st_expr:
  291.                                 opt4(&block->exp);
  292.                                 scanexpr(block->exp,0,0);
  293.                                 break;
  294.                         case st_while:
  295.                         case st_do:
  296.                                 opt4(&block->exp);
  297.                                 scanexpr(block->exp,0,0);
  298.                                 scan(block->s1);
  299.                                 break;
  300.                         case st_for:
  301.                                 opt4(&block->label);
  302.                                 scanexpr(block->label,0,0);
  303.                                 opt4(&block->exp);
  304.                                 scanexpr(block->exp,0,0);
  305.                                 scan(block->s1);
  306.                                 opt4(&block->s2);
  307.                                 scanexpr(block->s2,0,0);
  308.                                 break;
  309.                         case st_if:
  310.                                 opt4(&block->exp);
  311.                                 scanexpr(block->exp,0,0);
  312.                                 scan(block->s1);
  313.                                 scan(block->s2);
  314.                                 break;
  315.                         case st_switch:
  316.                                 opt4(&block->exp);
  317.                                 scanexpr(block->exp,0,0);
  318.                                 scan(block->s1);
  319.                                 break;
  320.                         case st_case:
  321.                                 scan(block->s1);
  322.                                 break;
  323.                                                 case st_block:
  324.                                                                 scan(block->exp);
  325.                                                                 break;
  326.                                                 case st_asm:
  327.                                                                 if (block->exp)
  328.                                                                     asm_scan(block->exp);
  329.                                                                 break;
  330.                         }
  331.                 block = block->next;
  332.                 }
  333. }
  334.  
  335. void exchange(CSE **c1)
  336. /*
  337.  *      exchange will exchange the order of two expression entries
  338.  *      following c1 in the linked list.
  339.  */
  340. {       CSE      *csp1, *csp2;
  341.         csp1 = *c1;
  342.         csp2 = csp1->next;
  343.         csp1->next = csp2->next;
  344.         csp2->next = csp1;
  345.         *c1 = csp2;
  346. }
  347.  
  348. int     desire(CSE *csp)
  349. /*
  350.  *      returns the desirability of optimization for a subexpression.
  351.  */
  352. {       if( csp->voidf || (isintconst(csp->exp->nodetype) &&
  353.                         csp->exp->v.i < 16 && csp->exp->v.i >= 0))
  354.                 return 0;
  355.         if( lvalue(csp->exp) )
  356.                 return 2 * csp->uses;
  357.         return csp->uses;
  358. }
  359.  
  360. int     bsort(CSE **list)
  361. /*
  362.  *      bsort implements a bubble sort on the expression list.
  363.  */
  364. {       CSE      *csp1, *csp2;
  365.         csp1 = *list;
  366.         if( csp1 == 0 || csp1->next == 0 )
  367.                 return 0;
  368.         bsort( &(csp1->next));
  369.         csp2 = csp1->next;
  370.         if( desire(csp1) < desire(csp2) ) {
  371.                 exchange(list);
  372.                 return 1;
  373.                 }
  374.         return 0;
  375. }
  376.  
  377. void repexpr(ENODE *node, int size)
  378. /*
  379.  *      repexpr will replace all allocated references within an expression
  380.  *      with tempref nodes.
  381.  */
  382. {       CSE      *csp;
  383.         if( node == 0 )
  384.                 return;
  385.                 if (size == 0)
  386.                     size = natural_size(node);
  387.         switch( node->nodetype ) {
  388.                 case en_rcon: case en_lrcon: case en_fcon:
  389.                 case en_icon:
  390.                                 case en_lcon:
  391.                                 case en_iucon:
  392.                                 case en_lucon:
  393.                                 case en_ccon:
  394.                 case en_nacon:
  395.                 case en_napccon:
  396.                                 case en_absacon:
  397.                 case en_autocon:
  398.                                 case en_autoreg:
  399.                         if( (csp = searchnode(node)) != 0 )
  400.                                 if( csp->reg > 0 ) {
  401.                                         node->nodetype = en_tempref;
  402.                                         node->v.i = csp->reg | (size << 8);
  403.                                         }
  404.                         break;
  405.                                 case en_floatref:
  406.                                 case en_doubleref:
  407.                                 case en_longdoubleref:
  408.                 case en_ub_ref:
  409.                 case en_uw_ref:
  410.                 case en_b_ref:
  411.                 case en_w_ref:
  412.                 case en_l_ref:
  413.                 case en_ul_ref:
  414.                         if( (csp = searchnode(node)) != 0 ) {
  415.                                 if( csp->reg > 0 ) {
  416.                                         node->nodetype = en_tempref;
  417.                                         node->v.i = csp->reg | (size << 8);
  418.                                         }
  419.                                 else
  420.                                         repexpr(node->v.p[0],0);
  421.                                 }
  422.                         else
  423.                                 repexpr(node->v.p[0],0);
  424.                         break;
  425.                 case en_uminus: case en_bits:
  426.                 case en_not:    case en_compl:
  427.                 case en_ainc:   case en_adec:
  428.                         repexpr(node->v.p[0],0);
  429.                         break;
  430.                                 case en_cb: case en_cub:
  431.                                 case en_cw: case en_cuw:
  432.                                 case en_cl: case en_cul:
  433.                                 case en_cf: case en_cd: case en_cp: case en_cld:
  434.                         repexpr(node->v.p[0],natural_size(node));
  435.                         break;
  436.                 case en_add:    case en_sub:
  437.                 case en_umul:    case en_udiv: case en_umod:
  438.                 case en_mul:    case en_div:
  439.                 case en_mod:    case en_lsh:
  440.                                 case en_asalsh: case en_asarsh: case en_alsh: case en_arsh:
  441.                 case en_rsh:    case en_and:
  442.                 case en_or:     case en_xor:
  443.                 case en_land:   case en_lor:
  444.                 case en_eq:     case en_ne:
  445.                 case en_lt:     case en_le:
  446.                                 case en_ugt:    case en_uge: case en_ult: case en_ule:
  447.                 case en_gt:     case en_ge:
  448.                 case en_cond:   case en_void:
  449.                 case en_asadd:  case en_assub:
  450.                 case en_asmul:  case en_asdiv:
  451.                 case en_asor:   case en_asand:   case en_asxor:
  452.                 case en_asmod:  case en_aslsh:
  453.                                 case en_asumod: case en_asudiv: case en_asumul: case en_pmul:
  454.                 case en_asrsh:  case en_fcall: case en_trapcall: case en_pdiv:
  455.                                 case en_pfcall: case en_pfcallb:
  456.                 case en_assign: case en_intcall: case en_fcallb: case en_refassign:
  457.                 case en_moveblock: case en_stackblock: case en_callblock:
  458.                                 case en_pcallblock:
  459.                         repexpr(node->v.p[0],0);
  460.                         repexpr(node->v.p[1],0);
  461.                         break;
  462.                 }
  463. }
  464.  
  465. void repcse(SNODE *block)
  466. /*
  467.  *      repcse will scan through a block of statements replacing the
  468.  *      optimized expressions with their temporary references.
  469.  */
  470. {       while( block != 0 ) {
  471.                 switch( block->stype ) {
  472.                         case st_return:
  473.                         case st_expr:
  474.                                 repexpr(block->exp,0);
  475.                                 break;
  476.                         case st_while:
  477.                         case st_do:
  478.                                 repexpr(block->exp,0);
  479.                                 repcse(block->s1);
  480.                                 break;
  481.                         case st_for:
  482.                                 repexpr(block->label,0);
  483.                                 repexpr(block->exp,0);
  484.                                 repcse(block->s1);
  485.                                 repexpr(block->s2,0);
  486.                                 break;
  487.                         case st_if:
  488.                                 repexpr(block->exp,0);
  489.                                 repcse(block->s1);
  490.                                 repcse(block->s2);
  491.                                 break;
  492.                         case st_switch:
  493.                                 repexpr(block->exp,0);
  494.                                 repcse(block->s1);
  495.                                 break;
  496.                         case st_case:
  497.                                 repcse(block->s1);
  498.                                 break;
  499.                                                 case st_block:
  500.                                                                 repcse(block->exp);
  501.                                                                 break;
  502.                                                 case st_asm:
  503.                                                                 if (block->exp)
  504.                                                                     asm_repcse(block->exp);
  505.                                                                 break;
  506.                         }
  507.                 block = block->next;
  508.                 }
  509. }
  510. void allocstack(void)
  511. /*
  512.  * This allocates space for local variables
  513.  * we do this AFTER the register optimization so that we can
  514.  * avoid allocating space on the stack twice
  515.  */
  516. {
  517.     int lvl = 0;
  518.     int again = TRUE;
  519.     int oldauto, max;
  520.     lc_maxauto = max = 0;
  521.     while (again) {
  522.         LIST *t = varlisthead;
  523.         int align;
  524.         lvl ++;
  525.         oldauto = max;
  526.         again = FALSE;
  527.         while (t) {
  528.             SYM *sp = t->data;
  529.             while (sp && (sp->inreg || sp->funcparm || sp->storage_class == sc_static || sp->storage_class == sc_label || sp->storage_class == sc_ulabel))
  530.                 sp = sp->next;
  531.             if (!sp) {
  532.                 t = t->link;
  533.                 continue;
  534.             }
  535.             if (sp->value.i >= lvl)
  536.                 again = TRUE;
  537.             if (sp->value.i == lvl) {
  538.                 lc_maxauto = oldauto;
  539.                 while (sp) {
  540.                     if (!sp->inreg && !sp->funcparm && sp->storage_class != sc_static) {
  541.                         int val;
  542.                         align = getalign(sc_auto,sp->tp);
  543.                         val = lc_maxauto % align;
  544.                         if (val != 0)
  545.                             lc_maxauto += align - val;
  546.                         lc_maxauto += sp->tp->size;
  547.                         sp->value.i = -lc_maxauto;
  548.                     }
  549.                     sp = sp->next;
  550.                 }
  551.             }
  552.             if (lc_maxauto > max)
  553.                 max = lc_maxauto;
  554.             t = t->link;
  555.         }
  556.     }
  557.     lc_maxauto = max;
  558.     lc_maxauto += stackadd;
  559.     lc_maxauto &= stackmod;
  560. }
  561. void opt1(SNODE *block)
  562. /*
  563.  *      opt1 is the externally callable optimization routine. it will
  564.  *      collect and allocate common subexpressions and substitute the
  565.  *      tempref for all occurrances of the expression within the block.
  566.  *
  567.  *        optimizer is currently turned off...
  568.  */
  569. {
  570.         int datareg = cf_freedata;
  571.         int addreg = 16 + cf_freeaddress;
  572.         int floatreg = 32 + cf_freefloat;
  573.         olist = 0;
  574.         scan(block);            /* collect expressions */
  575.                 voidall();                            /* Disallow regs whose address is taken  */
  576.                 voidfloat(block);                        /* disallow optimizing things which are assigned values derived from floats */
  577.                 reserveregs(&datareg, &addreg, &floatreg);        /* Allocate register vars */
  578.         allocate(datareg, addreg,floatreg,block);             /* allocate registers  for opt*/
  579.         repcse(block);          /* replace allocated expressions */
  580.                 loadregs();                        /* Initialize allocated regs */
  581. }